package 斐波那契数列;

/**
 * 求斐波那契数列第N位的值
 * <p>
 * 暴力递归
 * 去重递归
 * 双指针迭代
 */
public class Solution {
    public static void main(String[] args) {
        int v = calculate(10);
        System.out.println("v = " + v);

        v = calculate(10, new int[11]);
        System.out.println("v = " + v);

        v = twoPointIterater(10);
        System.out.println("v = " + v);
    }

    /**
     * 暴力递归
     */
    public static int calculate(int num) {
        if (num == 0 || num == 1) {
            return num;
        }
        return calculate(num - 1) + calculate(num - 2);
    }

    /**
     * 去重递归
     */
    public static int calculate(int num, int[] cache) {
        if (num == 0 || num == 1) {
            return num;
        }

        if (cache[num] != 0) {
            return cache[num];
        }

        cache[num] = calculate(num - 1, cache) + calculate(num - 2, cache);
        return cache[num];
    }

    /**
     * 双指针迭代（推荐）
     */
    public static int twoPointIterater(int num) {
        if (num == 0 || num == 1) {
            return num;
        }

        int l = 0, h = 1;
        for (int i = 2; i < num; i++) {
            int sum = l + h;
            l = h;
            h = sum;
        }

        return l + h;
    }

}
